package Demo76;


import java.util.Deque;
import java.util.LinkedList;

/**
 * 二叉树最大宽度
 * https://leetcode.cn/problems/maximum-width-of-binary-tree/submissions/562780295/
 */

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        // 创建一个队列
        Deque<Pairc> queue = new LinkedList<>();
        // 将根节点放入队列中
        queue.add(new Pairc(root,1));
        int ret = 0;
        // 遍历
        while(!queue.isEmpty()) {
            // 此处就是, 用该层的右节点的下标 - 右节点的下标 + 1, 就能拿到该层的个数
            if((queue.getLast().val - queue.getFirst().val + 1) > ret) {
                ret = queue.getLast().val - queue.getFirst().val + 1;
            }
            int sz = queue.size();
            for(int i = 0; i < sz; i++) {
                Pairc pairc = queue.poll();
                TreeNode node = pairc.treeNode;
                // 此处的 *2 和 *2 + 1 就是二叉树的定义, 子节点是父节点的下标*2/*2 + 1
                if(node.left != null) queue.add(new Pairc(node.left, pairc.val * 2));
                if(node.right != null) queue.add(new Pairc(node.right, pairc.val * 2 + 1));
            }
        }
        return ret;
    }
}